/**
 * 子集 2
 *
 * 给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的 子集（幂集）。
 * 解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。
 *
 * 示例 1：
 * 输入：nums = [1,2,2]
 * 输出：[[],[1],[1,2],[1,2,2],[2],[2,2]]
 *
 * 示例 2：
 * 输入：nums = [0]
 * 输出：[[],[0]]
 *
 * 提示：
 * 1 <= nums.length <= 10
 * -10 <= nums[i] <= 10
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 我们这里采用的是选和不选, 咱面临一个数的时候, 有两种解决方法
 * 就是选和不选, 要是没有相同的元素的话我们可以直接选择, 但是这题
 * 是可能有相同的元素的, 所以我们要排除这些相同的可能
 * 假设我们 x y 相邻 且 x == y, 于是我们的 选 x 不选 y, 与
 * 不选 x 和 选 y 的时候是一样的集合, 这个时候我们要是将 不选 x
 * 之前来对后面相同的进行相等判断, 就可以舍掉这种可能
 * 时间复杂度 : O(n ^ (2 ^ n))
 * 空间复杂度 : O(n)
 */

public class Main {

    // 定义全局变量
    List<List<Integer>> lists;
    List<Integer> list;
    int[] nums;
    int n;

    public List<List<Integer>> subsetsWithDup(int[] numss) {

        // 初始化
        lists = new ArrayList<>();
        list = new ArrayList<>();
        nums = numss;
        n = nums.length;

        // 这里我们将数组进行排序
        // 把相同的元素放在一起
        Arrays.sort(nums);

        // 从 0 下标开始遍历
        dfs (0);

        // 返回结果
        return lists;
    }

    private void dfs (int k) {

        // 当下标到达边界的时候, 将结果加入结果集
        if (k == n) {
            lists.add(new ArrayList<>(list));
            return;
        }


        // 选
        list.add(nums[k]);

        dfs(k + 1);

        // 恢复现场
        list.remove(list.size() - 1);

        // 这里我们要将一样的数给排除, 直到最后一个相同的数字
        while (k + 1 < n && nums[k] == nums[k + 1]) {
            k++;
        }

        // 不选
        dfs (k + 1);

        // 这里 选 和 不选, 不能反过来, 因为这里舍掉是就相当与这个位置没选
        // 所以判断的时候要在不选的前面, 而不是选的前面
    }
}